package com.torlesse.leetcode.algorithm.common;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: torlesse-liang
 * @Date: 2022/03/04/21:43
 * @Description: 插入排序
 */
public class InsertSort {
    public static void main(String[] args) {
//        insertSort(Swap.array);
        insertSort2(Swap.array);
        Swap.print(Swap.array);
    }

    /**
     * 插入排序
     * 用后一项元素与当前项进行比较，如果后一项<当前项，交换位置，保证每一次遍历最小元素归位
     * 此处：从小到大排序
     * @param array
     */
    public static void insertSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            //后一项元素 j = i +1;
            for (int j = i + 1; j > 0 ; j--) {
                //后一项与当前项比较
                if(array[j] < array[j - 1]){
                    Swap.swap(array,j,j-1);
                }
            }
        }
    }

    /**
     * 改进
     * 第一次遍历时直接从i=1开始，默认第0项已经归位
     * @param array
     */
    public static void insertSort2(int[] array){
        //i=1 : 默认第0项已经归位
        for (int i = 1; i < array.length; i++) {
            int j = 0;
            int current =  array[i];
            // i-1 当前项的上一项，上一项与当前项比较满足: array[j] > current
            for (j = i - 1; j >= 0 && array[j] > current ; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = current;
        }
    }
}
